/*
 * Copyright (c) 2010, 2011
 *	Open Source Technologies Ltd.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the company nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COMPANY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
#ifndef __BLISS64_RBTREE_H__
#define __BLISS64_RBTREE_H__

#define RBTREE_MAGIC      0xF1450000
#define RBTREE_DEAD       0xF145DEAD
#define RBTREE_ITEM_MAGIC 0x92C80000
#define RBTREE_ITEM_DEAD  0x92C8DEAD

#ifndef __RBTREE_T__
#define __RBTREE_T__
typedef struct rbtree_st rbtree_t;
#endif /* !__RBTREE_T__ */

#ifndef __RBTREE_ITEM_T__
#define __RBTREE_ITEM_T__
typedef struct rbtree_item_st rbtree_item_t;
#endif /* !__RBTREE_ITEM_T__ */

enum rbtree_colors
{
	tc_black,
	tc_red
};

struct rbtree_st
{
	uint32_t       t_magic;
	size_t         t_count;
	rbtree_item_t *t_root;
	comparator_t   t_comparator;
};

#define is_rbtree(obj)      is_object(obj, t_magic, RBTREE_MAGIC)
#define is_rbtree_dead(obj) is_object_dead(obj, t_magic, RBTREE_MAGIC)
#define is_rbtree_opt(obj)  is_object_opt(obj, t_magic, RBTREE_MAGIC)

struct rbtree_item_st
{
	uint32_t       ti_magic;
	rbtree_t      *ti_tree;
	rbtree_item_t *ti_parent;
	rbtree_item_t *ti_left;
	rbtree_item_t *ti_right;
	int            ti_color;
	intptr_t       ti_key;
	intptr_t       ti_value;
};

#define is_rbtree_item(obj)      is_object(obj, ti_magic, RBTREE_ITEM_MAGIC)
#define is_rbtree_item_dead(obj) is_object_dead(obj, ti_magic, RBTREE_ITEM_MAGIC)
#define is_rbtree_item_opt(obj)  is_object_opt(obj, ti_magic, RBTREE_ITEM_MAGIC)

__begin_decls

rbtree_t *rbtree_create     __p((comparator_t cmp));
void      rbtree_initialize __p((rbtree_t *tree, comparator_t cmp));

#ifndef NDEBUG

size_t rbtree_size __p((rbtree_t *tree));

#else /* NDEBUG */

#define rbtree_size(tree) ((tree)->t_count)

#endif /* NDEBUG */

rbtree_item_t *rbtree_insert    __p((rbtree_t *tree, intptr_t key, intptr_t val));
rbtree_item_t *rbtree_replace   __p((rbtree_t *tree, intptr_t key, intptr_t val));
rbtree_item_t *rbtree_find      __p((rbtree_t *tree, intptr_t key));
rbtree_item_t *rbtree_get_first __p((rbtree_t *tree));
rbtree_item_t *rbtree_get_last  __p((rbtree_t *tree));

#ifndef NDEBUG

intptr_t rbtree_item_get_key    __p((rbtree_item_t *item));
void     rbtree_item_set_value  __p((rbtree_item_t *item, intptr_t val));
intptr_t rbtree_item_get_value  __p((rbtree_item_t *item));

#else /* NDEBUG */

#define rbtree_item_get_key(item)        ((item)->ti_key)
#define rbtree_item_set_value(item, val) ((item)->ti_value = (val))
#define rbtree_item_get_value(item)      ((item)->ti_value)

#endif /* NDEBUG */

rbtree_item_t *rbtree_item_get_prev __p((rbtree_item_t *item));
rbtree_item_t *rbtree_item_get_next __p((rbtree_item_t *item));
rbtree_item_t *rbtree_item_delete   __p((rbtree_item_t *item));

void      rbtree_finalize __p((rbtree_t *tree));
rbtree_t *rbtree_destroy  __p((rbtree_t *tree));

__end_decls

#endif /* !__BLISS64_RBTREE_H__ */
